// @algorithm @lc id=394 lang=cpp 
// @title decode-string


// @test("3[a]2[bc]")="aaabcbc"
// @test("3[a2[c]]")="accaccacc"
// @test("2[abc]3[cd]ef")="abcabccdcdcdef"
// @test("abc3[cd]xyz")="abccdcdcdxyz"
#define IS_DIGIT(ch) ('0'<=(ch) && (ch)<='9')
#define IS_LETTER(ch) ('a'<=(ch) && (ch)<='z')
class Solution {
public:
    string decodeString(string s) {
        auto pc = s.begin();

        function<int()> parseNum = [&](){
            int n = 0;
            while(pc!=s.end() && IS_DIGIT(*pc)){
                n = n*10 + (*pc - '0');
                pc++;
            }
            return n;
        };

        function<string()> decode = [&]()->string{
            if(pc==s.end() || *pc==']') return "";
            string res;
            if(IS_DIGIT(*pc)){
                int n = parseNum();
                pc++;
                string w = decode();
                pc++;
                while(n--) res += w;
            }
            while(pc!=s.end() && IS_LETTER(*pc))
                res += *pc++;
            return res + decode();
        };
        return decode();
    }
};